#!/usr/bin/python3
# -*- coding:utf-8 -*-
# __author__ == taoyulong2018@gmail.com
# __time__ == 2023/8/17 9:58
# ===========================================
#       题目名称： 3. 无重复字符的最长子串
#       题目地址： https://leetcode.cn/problems/longest-substring-without-repeating-characters/
#       题目描述： https://note.youdao.com/s/RRXNSXjR
# ===========================================


class Solution:
    """
        实现逻辑：
            分三步走，下一个字符串在stack中的位置
            前 删除最前面那个元素
            中 获取这个元素在stack中出现的位置，进而进行截取
            后 清空stack，添加新元素
    """
    def lengthOfLongestSubstring(self, s):
        stack = []
        max_count = 0
        for i in range(len(list(s))):
            if stack:
                if s[i] in stack:
                    # 判断是否是 前面相同 还是后面相同
                    if stack[0] == s[i]:  # 前
                        del stack[0]
                        stack.append(s[i])
                    elif stack[-1] == s[i]:  # 后
                        stack.clear()
                        stack.append(s[i])
                    elif s[i] in stack:  # 中间
                        j = 0
                        while j < len(stack) and stack[j] != s[i]:
                            j += 1
                        stack = stack[j+1:]
                        stack.append(s[i])
                else:
                    stack.append(s[i])
            else:
                stack.append(s[i])
            max_count = max(max_count, len(stack))
        return max_count


if __name__ == '__main__':
    s = Solution()
    # 3
    print(s.lengthOfLongestSubstring(s="abcabcbb"))
    # 1
    print(s.lengthOfLongestSubstring(s="bbbbb"))
    # 3
    print(s.lengthOfLongestSubstring(s="pwwkew"))
    # 2
    print(s.lengthOfLongestSubstring(s="aab"))
    # 5
    print(s.lengthOfLongestSubstring(s="ckilbkd"))
